#include "BTreeNode.h"

using namespace std;
/*
0f 1024 bytes
4 bytes to point to next node
4 bytes to keep count of number of keys
1024-8 = 1016 bytes left
12 bytes per entry per
84*12 = 1008 bytes
total = 1008 + 8  = 1016 bytes used with each node allowed 84 entries
*/

BTLeafNode::BTLeafNode()
{
	memset(buffer, 0, PageFile::PAGE_SIZE);					//sets the entire buffer to 0 
}

RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
	RC readError = pf.read(pid, buffer);
    return readError; 
}
    
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
    RC writeError = pf.write(pid, buffer);
    return writeError; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 

	int keyCount = 0;
	memcpy(&keyCount, &buffer, sizeof(int));
	return keyCount; 
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
	int ridSize = sizeof(RecordId);
	int keySize = sizeof(int);
	int entrySize = ridSize + keySize;					
	int nodeSize = getKeyCount() * entrySize;			
	int pidSize = sizeof(PageId);
	int numKey = getKeyCount();

	char* iter = &(buffer[0]);
	int i = 0;
	
	if(getKeyCount() >= 84) 					//each node can only have up to 84 keys
	{
		return RC_NODE_FULL;
	}
	iter += sizeof(int);
	iter += pidSize;

	int currentKey;
	
	//move pointer along buffer until it reaches end of current entries
	for(int trackKey = 1; trackKey <= numKey; trackKey++)
	{
		memcpy(&currentKey, iter, keySize);
		//cout << "currKey is " << currKey << endl;
		if(currentKey == 0) 
		{
			break;
		}
		if (currentKey < key) 
		{
			iter += entrySize;
			i++;
		} 
		else 
		{
			break;
		}
	}

	if (&(buffer[PageFile::PAGE_SIZE]) - iter < 16)				//16 or 20? need to check
	{
		return RC_NODE_FULL;
	}

	char* backup = (char*)malloc(PageFile::PAGE_SIZE * sizeof(char));	//cplusplus reference
	memset(backup, 0, PageFile::PAGE_SIZE);
	if(nodeSize > 0 && currentKey != 0) 
	{
		memcpy(backup, iter, nodeSize - (entrySize * i));			//stores entries larger than inserting entry
		memset(iter, 0, nodeSize - (entrySize * i));				//and sets all values to 0 ahead of iter
	}

	memcpy(iter, &key, keySize);									//copies key to iter
	iter += keySize;
	memcpy(iter, &rid, ridSize);									//copies recordId to iter
	iter += ridSize;
	if(nodeSize > 0 && currentKey != 0) 
	{
		memcpy(iter, backup, nodeSize- (entrySize * i));			//copies back the other values ahead of iter
	}
	
	free(backup);													//note:malloc uses free not delete

	int currentKeyCount = numKey;									//finds number of key to increase count
	currentKeyCount++;
	iter = &(buffer[0]);											//moves iter back to beginning
	memcpy(iter, &currentKeyCount, keySize);						//update keyCount in buffer

	return 0; 
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
	int ridSize = sizeof(RecordId);
	int keySize = sizeof(int);
	int entrySize = ridSize + keySize;					
	int nodeSize = getKeyCount() * entrySize;			
	int pidSize = sizeof(PageId);
	int numKey = getKeyCount();
	
	char* iter = &(buffer[0]);
	
	iter += sizeof(int);
	iter += pidSize;
	
	for(int i = 0; i < numKey/2; i++)
	{
		iter += entrySize;
	}
	// while(i < (numKey / 2)) 
// 	{
// 		iter += entrySize;
// 		i++;
// 	}

	char* backup = (char*)malloc(1024*sizeof(char));
	//char* head = backup;
	
	//allocate memory and copy 2nd half of node
	memset(backup, 0, 1024*sizeof(char));
	memcpy(backup, iter, nodeSize - (entrySize * (numKey/2)));


	//remove 2nd half of node from current node
	memset(iter, 0, nodeSize - (entrySize * (numKey/2)));
	int newKey = numKey / 2;
	memcpy(buffer, &newKey, keySize);

	//call insert to copy data into new node
	while(backup) 
	{
		int j;
		RecordId r;
		memcpy(&j, backup, sizeof(int));
		if(j == 0) 
		{
			break;
		}
		backup += sizeof(int);
		memcpy(&r, backup, ridSize);
		backup += ridSize;

		if( sibling.insert(j, r) != 0 ) 
		{
			free(backup);
			return RC_FILE_WRITE_FAILED;
		}
	}

	free(backup);

	//store the first key in siblingKey
	RecordId r;
	if( sibling.readEntry(0, siblingKey, r) != 0) 
	{
		return RC_FILE_READ_FAILED;
	}

	//insert the new key
	if(key < siblingKey) 
	{
		if( insert(key, rid) != 0 ) 
		{
			return RC_FILE_WRITE_FAILED;
		}
	} 
	else 
	{
		if( sibling.insert(key, rid) != 0 ) {
		
			return RC_FILE_WRITE_FAILED;
		}
	}
	//check again
	if( sibling.readEntry(0, siblingKey, r) != 0) 
	{
		return RC_FILE_READ_FAILED;
	}

	return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
	int currentKey;
	int numKey = getKeyCount();
	int i = 0;
	int ridSize = sizeof(RecordId);
	int keySize = sizeof(int);
	int entrySize = ridSize + keySize;	
	char* iter= &(buffer[0]);

	iter += sizeof(int);								//move pointer to key
	
	for(int trackKey = 1; trackKey <= numKey; trackKey++)
	{
		memcpy(&currentKey, iter, keySize);
		if(currentKey >= searchKey || currentKey == 0) 
		{
			eid = i;
			break;
		}
		iter += entrySize;							//move to next key
		i++;
	}
	// while(trackKey <= getKeyCount()) 
// 	{
// 		memcpy(&currentKey, iter, keySize);
// 		if(currentKey >= searchKey || currentKey == 0) 
// 		{
// 			eid = i;
// 			break;
// 		}
// 		i++;
// 		trackKey++;
// 		iter += entrySize;
// 	}

	return 0; 
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	int numKey = getKeyCount();
	int trackKey = 1;
	int ridSize = sizeof(RecordId);
	int keySize = sizeof(int);
	int pidSize = sizeof(PageId);
	int entrySize = ridSize + keySize;
	char* iter = &(buffer[0]);
	int i = 0;													//first entry is 0
	
	iter += sizeof(int);
	iter += pidSize;											//points to first entry
	
	while(trackKey <= numKey && i < eid) 
	{
		iter += entrySize;
		i++;
		trackKey++;
	}
	memcpy(&key, iter, keySize);
	iter += keySize;
	memcpy(&rid, iter, ridSize);
	return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
	PageId pid;
	int pidSize = sizeof(PageId);
	char* iter = &(buffer[0]);
	iter += sizeof(int);
	memcpy(&pid, iter, pidSize);

	return pid;  
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
	char* iter = &(buffer[0]);
	iter += sizeof(int);

	memcpy(iter, &pid, sizeof(PageId));

	return 0; 
}

//same idea of implementation as leaf node
BTNonLeafNode::BTNonLeafNode()
{
	memset(buffer, 0, PageFile::PAGE_SIZE);					//sets the buffer to 0 
}
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
	RC readError = pf.read(pid, buffer);
    return readError; 
}
    
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
    RC writeError = pf.write(pid, buffer);
    return writeError; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	//same as leaf node
	int keyCount = 0;
	memcpy(&keyCount, &buffer, sizeof(int));
	return keyCount; 
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{	
	//same idea as LeafNode insert but adjusting for pageId instead of recordId
	int keySize = sizeof(int);				
	int pidSize = sizeof(PageId);
	int entrySize = pidSize + keySize;
	int numKey = getKeyCount();
	int nodeSize = entrySize * numKey;
	char* iter = &(buffer[0]);
	int i = 0;

	if(nodeSize >= PageFile::PAGE_SIZE - entrySize) 		//no room for new entries
	{
		return RC_NODE_FULL;
	}

	//skip number of keys, skip first pid
	iter += sizeof(int);
	iter += pidSize;

	int currentKey;
	while (iter) 
	{
		memcpy(&currentKey, iter, keySize);
		if(currentKey == 0) 
		{
			break;
		}
		if (currentKey < key) 
		{
			iter += entrySize;
			i++;
		} 
		else 
		{
			break;
		}
	}

	if(currentKey == key) 
	{
		iter += sizeof(int);
		memcpy(iter, &pid, pidSize);
		return 0;
	}

	if (iter == &(buffer[PageFile::PAGE_SIZE]))
	{
		return RC_FILE_WRITE_FAILED;
	}

	char* backup = (char*) malloc(PageFile::PAGE_SIZE * sizeof(char));
	memset(backup, 0, PageFile::PAGE_SIZE);


	if(nodeSize > 0 && currentKey != 0) 
	{
		memcpy(backup, iter, nodeSize - (entrySize * i));
		memset(iter, 0, nodeSize - (entrySize * i));
	}
	
	memcpy(iter, &key, keySize);
	iter += sizeof(int);
	memcpy(iter, &pid, pidSize);
	iter += pidSize;
	if(nodeSize > 0 && currentKey != 0) 
	{
		memcpy(iter, backup, nodeSize - (entrySize * i));
	}
	free(backup);

	int currentKeyCount = numKey;
	currentKeyCount++;
	iter = &(buffer[0]);
	memcpy(iter, &currentKeyCount, sizeof(int)); 
	
	return 0; 
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	int keySize = sizeof(int);
	int pidSize = sizeof(PageId);
	int entrySize = keySize + pidSize;
	int numKey = getKeyCount();
	int nodeSize = entrySize * numKey;
	char* iter = &(buffer[0]);
	iter += sizeof(int);
	
	int i = 0;
	while(i < (numKey / 2)) 
	{
		iter += entrySize;
		i++;
	}
	
	char* backup = (char*) malloc(PageFile::PAGE_SIZE * sizeof(char));
	//char* head = backup;
	//copy 2nd half of data elsewhere
	memset(backup, 0, 1024*sizeof(char));
	memcpy(backup, iter,nodeSize - (entrySize * (numKey / 2)));

	//set data after iter to 0
	memset(iter, 0, nodeSize - (entrySize * (numKey / 2)));
	int newKey = numKey / 2;
	memcpy(buffer, &newKey, keySize);				//reduce keys in the node after taking out half entries

	//call insert for data into the new node
	while(backup) 
	{
		int j;
		PageId p;
		memcpy(&j, backup, sizeof(int));
		if(j == 0) 
		{
			break;
		}
		backup += sizeof(int);
		memcpy(&p, backup, pidSize);
		backup += pidSize;
		if( sibling.insert(j, p) != 0) 
		{
			free(backup);
			return RC_FILE_WRITE_FAILED;
		}
	}

	free(backup);


	//insert the new key that we're trying to insert
	if(key < midKey) 
	{
		if( insert(key, pid) != 0 )
		{
			return RC_FILE_WRITE_FAILED;
		}
	} 
	else 
	{
		if( sibling.insert(key, pid) != 0 ) 
		{
			return RC_FILE_WRITE_FAILED;
		}
	}

	return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
	int numKey = getKeyCount();
	int trackKey = 1;
	int ridSize = sizeof(RecordId);
	int keySize = sizeof(int);
	int pidSize = sizeof(PageId);
	int entrySize = ridSize + keySize;
	
	char* iter = &(buffer[0]);
	int currentkey;

	iter += sizeof(int);
	iter += sizeof(int);

	while(iter) 
	{
		memcpy(&currentkey, iter, sizeof(int));
		if(currentkey != 0 && currentkey < searchKey) 
		{
			iter += sizeof(int);
		} 
		else 
		{
			iter -= pidSize;
			memcpy(&pid, iter, pidSize);
			break;
		}
		iter += entrySize;
	}
	return 0; 
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	int pidSize = sizeof(PageId);
	int keySize = sizeof(int);
	int k = 1;
	char* iter = &(buffer[0]);
	iter += sizeof(int);

	memcpy(iter, &pid1, pidSize);
	iter += pidSize;
	memcpy(iter, &key, keySize);
	iter += keySize;
	memcpy(iter, &pid2, pidSize);
	memcpy(buffer, &k, sizeof(int)); 
	
	return 0; 
}
